package 笔试2.微软.two;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

//--合并区间-微软起重机问题
public class Main {

    public List<int[]> merge(int[][] intervals) {
        // 头同/不同 都 升序！
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            list.add(new int[]{intervals[i][0], intervals[i][1]});
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if(a[0] != b[0]){
                    return a[0]-b[0];
                }else {
                    return a[1]-b[1]; // 这是1 不是0
                }
            }
        });

        // 若消去while 需要初始化 l r
        int l = list.get(0)[0], r = list.get(0)[1]; // 新的[0]
        List<int[]> resList = new ArrayList<>(); // 要用新的list, 要不就误删 题干list的末尾了
        resList.add(new int[]{l,r});
        List<int[]> kongdangList = new ArrayList<>();
        //合并
        for (int i = 1; i < list.size(); i++) {
            int thisR = list.get(i)[1];
            int thisL = list.get(i)[0];
            // 删 覆盖 ( 14 23 )
            if(r >= thisR){
                continue;
            }
            // 相交
            else if(r >= thisL){
                r = thisR;
                resList.remove(resList.size()-1);
                resList.add(new int[]{l,r});
            }
            // 相离
            else if(r < thisL){
                l = thisL;
                r = thisR;
                resList.add(new int[]{l,r});
            }
        }
        return resList;
    }
    public boolean solution(int[] A, int[] P, int B, int E) {
        int N = A.length;
        int[][] g = new int[N][2];
        for (int i = 0; i < N; i++) {
            int b=A[i],a=P[i];
            int lf=a-b,rt=a+b;
            g[i][0]=lf;
            g[i][1]=rt;
        }
//        System.out.println(1);
        List<int[]> merge = merge(g);
//        System.out.println(1);
        for (int[] xy : merge) {
            int lf=xy[0],rt=xy[1];
            if(lf<=B && B<=rt && lf<=E && E<=rt){
                return true;
            }
        }
        return false;
    }

    @Test
    public void test() {
        int[] A = {2,1};
        int[] P = {5,1};
        int B=3;int E=6;
        System.out.println(solution(A, P, B, E));
    }
}
